Directed Acyclic Graphs(DAGs)

Content-addressing可能なデータ構造を作る前にその構造を正確かつ明確に定義する必要がある => Graphを利用する

Graph: Objectsの集まりの間の関係を表すのに使われる数学的抽象表現

Graph内のObjectをNode, Objects間の関係をEdge

ex: 2つの都市のペアを結ぶ道路、格好の生徒間の友人関係

https://scrapbox.io/files/64a38c6c00e566001bf78040.png

GraphがあればあるNodeから出発して、そのEdgeに沿って別のNodeに移動することが想像できる。Root Directoryのpicsから始めて、目的のファイルに到達するために階層を深くしていく

各辺が何らかの方向性を持っている場合である

上記の図だと、ディレクトリはファイルを内包するが、ファイルはディレクトリを内包しない

Node感の関係は一方向にのみ正しく関連する

ancestor, Descendent, Parent, Child

catsディレクトリに対応するノードは、2つのファイルノードの親となる

親を持たないNode -> Root directorys

子を持たないNode -> Leaf nodes

親と子の両方を持つNode -> Intermediate nodes

Intermediate nodesとRoot nodesの両方を指す -> Non-leaf

Graphにループがない場合、任意のNodeが与えられた時に、そのNodeからグラフの辺に沿ってそれ自身に戻るナビゲートがない = Acyclic

有向かつ無循環のグラフ